第 112 场力扣夜喵双周赛

判断通过操作能否让字符串相等 I

同下。

判断通过操作能否让字符串相等 II

模拟。也可以手动比较，就是适用性不好。（PS：想出一个写法，结果被自己 Hack 掉了~）

class Solution {
    public boolean checkStrings(String s1, String s2) {
        int n = s1.length();
        int[][] c1 = new int[2][26], c2 = new int[2][26];
        for (int i = 0; i < n; i++) {
            c1[i & 1][s1.charAt(i) - 'a']++;
            c2[i & 1][s2.charAt(i) - 'a']++;
        }
        return Arrays.deepEquals(c1, c2);
    }
}

几乎唯一子数组的最大和

滑动窗口。

class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        int n = nums.size();
        long sum = 0L, ans = 0L;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.merge(nums.get(i), 1, Integer::sum);
            sum += nums.get(i);
            if (i >= k - 1) {
                if (map.size() >= m) ans = Math.max(ans, sum);
                if (map.merge(nums.get(i - k + 1), -1, Integer::sum) == 0) {
                    map.remove(nums.get(i - k + 1));
                }
                sum -= nums.get(i - k + 1);
            }
        }
        return ans;
    }
}

统计一个字符串的 k 子序列美丽值最大的数目

因为和选择的顺序没有关系，所以贪心的选择出现次数最大的字母就行。

class Solution {
    private static final long MOD = (long) 1e9 + 7;

    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        char[] ss = s.toCharArray();
        int[] cnt = new int[26];
        for (char c : ss) {
            cnt[c - 'a']++;
        }
        TreeMap<Integer, Integer> map = new TreeMap<>((a, b) -> b - a);
        for (int i = 0; i < 26; i++) {
            map.merge(cnt[i], 1, Integer::sum);
        }
        long ans = 1L;
        for (var e : map.entrySet()) {
            int key = e.getKey(), val = e.getValue();
            if (val >= k) {
                return (int) (ans * comb(val, k) % MOD * pow(key, k) % MOD);
            }
            k -= val;
            ans = (ans * pow(key, val)) % MOD;
        }
        return 0;
    }
    
    private long pow(long x, int n) {
        long res = 1L;
        while (n != 0) {
            if ((n & 1) == 1) res = (res * x) % MOD;
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }

    private long comb(long n, int k) {
        long res = n;
        for (int i = 2; i <= k; i++) {
            res = res * --n / i;
        }
        return res % MOD;
    }
}